1. Field of the Invention
The present invention relates to a method of multiplying for a Galois field and a multiplier utilizing the Galois field multiplication method, and more particularly to a Galois field multiplication method and a multiplier utilizing the same, enabling an easy application to various cases by virtue of a generalization of algorithm and capable of minimizing the total number of gates used.
2. Description of the Prior Art
Error may be probably generated upon storing, transmitting and receiving digital signals. Such an error is difficult to be completely avoidable due to an effect caused by quantizing noise and the like basically present more or less in the nature. This means that to develop a device operable irrespective of the error is very prodigal. Consequently, a method has been generally used, in which an error estimated more or less is detected and corrected in accordance with a certain algorithm.
In such an error detecting and correcting method, error correction codes are used. Encoding and decoding of such error correction codes are realized on the basis of arithmetical theories relating to Galois field.
A set enabling an addition and a deduction, that is, closed for the addition and deduction operations is generally called an "Abelian group". A set enabling a multiplication in addition to the addition and deduction operations, that is, closed for the three operations including the multiplication operation is called a "ring". On the other hand, a set enabling the four arithmetical operations including a division in addition to the three operations, that is, closed for the four arithmetical operations is called a "field". Such a field may be a set of rational numbers and a set of real numbers.
Meanwhile, an error correction code is a set composed of a finite number of elements. Accordingly, such an error correction code requires a finite field which enables the four arithmetical operations and is closed for the four arithmetical operations. Such a finite field is generally called a "Galois field". In order to establish four arithmetical operations among finite elements of the Galois field and close the Galois field for the four arithmetical operations, the four arithmetical operations for the Galois field are defined differently from the general four arithmetical operations.
In re-defining the four arithmetical operations for the Galois field, multiplication is most important. For example, in a case of a most general Galois field which has 2.sup.N elements (N=1, 2, 3, . . . ), addition is easily calculated by exclusively ORing numbers of bits of individual elements. Deduction is calculated in the same manner as in the addition. On the other hand, division is calculated using an inversion table and the multiplication.
The Galois field which is a general 8-bit system has 2.sup.8 elements (2.sup.8 =256) and is denoted by GF(256). Characteristic of the Galois field is defined by a polynomial generating the Galois field. For example, GF(16) is expressed by a generated polynomial G(X) (G(X)=X.sup.4 +X+1). FIG. 1 is a multiplication table for GF(16).
In the multiplication table, X, X.sup.2 and X.sup.3 are regarded as 2, 4 and 8, respectively (X=2, X.sup.2 =4, X.sup.3 =8). The multiplication table also uses the generated polynomial G(X) (G(X)=X.sup.4 +X+1). In accordance with the Galois field theory, the following conditions are established: EQU 1+1=0 EQU X+X=0 EQU X.sup.2 +X.sup.2 =0 EQU X.sup.3 +X.sup.3 =0
When zero is substituted for the polynomial G(X) (G(X)=0) in accordance with the operation theory, the following condition is established: EQU X.sup.4 =X+1
For example, a multiplication of 7 by 8 (7.times.8) is processed as follows: ##EQU1##
Meanwhile, a general multiplication of (A.sub.3 X.sup.3 +A.sub.2 X.sup.2 +A.sub.1 X+A.sub.0).times.(B.sub.3 X.sup.3 +B.sub.2 X.sup.2 +B.sub.1 X+B.sub.0) is processed as follows: ##STR1##
Assuming that the above multiplication is processed for a Galois field, the addition in each bracket pair in the final result of the multiplication means the exclusive OR operation. A multiplier capable of achieving such a multiplication may be embodied in various manners. For example, where a multiplier is to be made only for the final result using 2-input AND gates and 2-input exclusive OR gates, it requires 22 AND gates and 18 exclusive OR gates.
In such a multiplier, however, it is difficult to carry out a debug. Moreover, an increased number of elements of a Galois field and an increased number of degrees of a generated polynomial results in a difficulty to manually calculate the multiplication. Since there is no common factor in the result of the calculation, it is difficult to optimize the multiplier.
A general multiplier for a Galois field GF(16) is a circuit which uses two kinds of cells and realizes a calculation of .gamma..times..beta.+.theta. for three elements .gamma., .beta. and .theta. of the Galois field, as shown in FIG. 2.
The elements .gamma., .beta. and .theta. can be expressed in the form of a polynomial as follows: EQU .gamma.(X)=.gamma..sub.3 X.sup.3 +.gamma..sub.2 X.sup.2 +.gamma..sub.1 X+.gamma..sub.0 EQU .beta.(X)=.beta..sub.3 X.sup.3 +.beta..sub.2 X.sup.2 +.beta..sub.1 X+.beta..sub.0 EQU .theta.(X)=.theta..sub.3 X.sup.3 +.theta..sub.2 X.sup.2 +.theta..sub.1 X+.theta..sub.0
Also, a multiplication of .gamma. by .beta. can be expressed as follows: EQU .gamma..multidot..beta.=.gamma.(X).multidot..beta.(X) mod G(X)
Assuming that .gamma..multidot..beta.=K.sub.3 X.sup.3 +K.sub.2 X.sup.2 +K.sub.1 X+K.sub.0, the following equation is established because mod G(X) is identical to G(X) of zero (G(X)=0): ##EQU2##
Cells in the first column of the multiplier shown in FIG. 2 execute the following operation: EQU .gamma..sup.(1) (X)=.gamma.(X) EQU .theta..sup.(1) (X)=.theta.(X)+.beta..sub.0 .gamma.(X)
Cells in the remaining i-th column of the multiplier execute the following operation: EQU .gamma..sup.(i+1) (X)+X .gamma..sup.(i) (X) mod G(X) EQU .theta..sup.(i+1) (X)+.theta..sup.(i) (X)+.beta..sub.i .gamma..sup.(i+1) (X)
Each cell executes two operations as follows: EQU .gamma..sub.j.sup.(i+1) =.gamma..sub.j-1.sup.i =.gamma..sub.3.sup.i .multidot.P.sub.j EQU .theta..sub.j.sup.(i+1) =.theta..sub.j-1.sup.(i) =.beta..sub.i .multidot..gamma..sub.j.sup.(i+1)
where, "A.sup.(i).sub.j " represents a cell positioned at the i-th column and the j-th row of a matrix of the multiplier.
In the first cell of the second column, for example, .gamma..sub.3 .beta..sub.1 are ANDed by an AND gate AD.sub.2.1. The result of the AND operation and .theta..sub.0.sup.(1) are exclusively ORed by an exclusive OR gate XOR.sub.2.1. The result of the exclusive OR operation is outputted as .theta..sub.0 (2). In the second cell, .gamma..sub.3.sup.(0) and .gamma..sub.0 are exclusively ORed by an exclusive OR gate XOR.sub.2.2. The result of the operation by the exclusive OR gate XOR.sub.2.2 is sent to an AND gate AD.sub.2.3.
The output from the exclusive OR gate XOR.sub.2.2 is then ANDed with another input .beta..sub.1 in the AND gate AD.sub.2.3. An output from the AND gate AD.sub.2.3 is exclusively ORed with .theta..sub.1.sup.(1) by an exclusive OR gate XOR.sub.2.3 which, in turn, outputs .theta..sub.1.sup.(1). In such a manner, all columns execute the calculation. Outputs at cells of the final column after completing the calculation are as follows: EQU .theta..sub.0.sup.(4) =W.sub.0 EQU .theta..sub.1.sup.(4) =W.sub.1 EQU .theta..sub.2.sup.(4) =W.sub.2 EQU .theta..sub.3.sup.(4) =W.sub.3
In such a conventional Galois field multiplier, however, flows of signals are obscure. Furthermore, the multiplier is difficult to extend to other Galois field such as GF(256). The multiplier has a disadvantage in that it is difficult to be applied for encoding and decoding of error correction code.